package everyday;

import java.util.*;
import java.util.concurrent.CopyOnWriteArraySet;

// https://leetcode.cn/problems/remove-invalid-parentheses/
public class Test35 {

//    private List<String> res = new ArrayList<String>();
//
//    public List<String> removeInvalidParentheses(String s) {
//        int lremove = 0;
//        int rremove = 0;
//
//        for (int i = 0; i < s.length(); i++) {
//            if (s.charAt(i) == '(') {
//                lremove++;
//            } else if (s.charAt(i) == ')') {
//                if (lremove == 0) {
//                    rremove++;
//                } else {
//                    lremove--;
//                }
//            }
//        }
//        helper(s, 0, lremove, rremove);
//
//        return res;
//    }
//
//    private void helper(String str, int start, int lremove, int rremove) {
//        if (lremove == 0 && rremove == 0) {
//            if (isValid(str)) {
//                res.add(str);
//            }
//            return;
//        }
//
//        for (int i = start; i < str.length(); i++) {
//            if (i != start && str.charAt(i) == str.charAt(i - 1)) {
//                continue;
//            }
//            // 如果剩余的字符无法满足去掉的数量要求，直接返回
//            if (lremove + rremove > str.length() - i) {
//                return;
//            }
//            // 尝试去掉一个左括号
//            if (lremove > 0 && str.charAt(i) == '(') {
//                helper(str.substring(0, i) + str.substring(i + 1), i, lremove - 1, rremove);
//            }
//            // 尝试去掉一个右括号
//            if (rremove > 0 && str.charAt(i) == ')') {
//                helper(str.substring(0, i) + str.substring(i + 1), i, lremove, rremove - 1);
//            }
//        }
//    }

    public static void main(String[] args) {
        List<String> list = removeInvalidParentheses("(a)())()");
        for (String s : list) {
            System.out.println(s);
        }
    }

    private static boolean isValid(String str) {
        int cnt = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                cnt++;
            } else if (str.charAt(i) == ')') {
                cnt--;
                if (cnt < 0) {
                    return false;
                }
            }
        }

        return cnt == 0;
    }


    static Set<String> res = new HashSet<>();

    public static List<String> removeInvalidParentheses(String s) {
        int lremove = 0, rremove = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') lremove++;
            else if (s.charAt(i) == ')') {
                if (lremove == 0) rremove++;
                else lremove--;
            }
        }
        helper(s, 0, lremove, rremove);
        return new ArrayList<>(res);
    }

    private static void helper(String str, int start, int lremove, int rremove) {
        if (lremove == 0 && rremove == 0) {
            if (isValid(str)) {
                res.add(str);
            }
            return;
        }
        for (int i = start; i < str.length(); i++) {
            if (lremove > 0 && str.charAt(i) == '(') {
                helper(str.substring(0, i) + str.substring(i + 1), i, lremove - 1, rremove);
            }
            if (rremove > 0 && str.charAt(i) == ')') {
                helper(str.substring(0, i) + str.substring(i + 1), i, lremove, rremove - 1);
            }
        }
    }

}
